// https://mp.weixin.qq.com/s/oXv03m1J8TwtHwMJEZ1ApQ

/*
1、调用get(key)方法时，要返回该key对应的val。

2、只要用get或者put方法访问一次某个key，该key的freq就要加一。

3、如果在容量满了的时候进行插入，则需要将freq最小的key删除，如果最小的freq对应多个key，则删除其中最旧的那一个。
*/

/*
1、使用一个HashMap存储key到val的映射，就可以快速计算get(key)。
HashMap<Integer, Integer> keyToVal;

2、使用一个HashMap存储key到freq的映射，就可以快速操作key对应的freq。
HashMap<Integer, Integer> keyToFreq;

3、这个需求应该是 LFU 算法的核心，所以我们分开说。

    3.1、首先，肯定是需要freq到key的映射，用来找到freq最小的key。

    3.2、将freq最小的key删除，那你就得快速得到当前所有key最小的freq是多少。想要时间复杂度 O(1) 的话，肯定不能遍历一遍去找，那就用一个变量minFreq来记录当前最小的freq吧。

    3.3、可能有多个key拥有相同的freq，所以 freq对key是一对多的关系，即一个freq对应一个key的列表。

    3.4、希望freq对应的key的列表是存在时序的，便于快速查找并删除最旧的key。

    3.5、希望能够快速删除key列表中的任何一个key，因为如果频次为freq的某个key被访问，那么它的频次就会变成freq+1，就应该从freq对应的key列表中删除，加到freq+1对应的key的列表中。

    HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
    int minFreq = 0;

    LinkedHashSet顾名思义，是链表和哈希集合的结合体。链表不能快速访问链表节点，但是插入元素具有时序；哈希集合中的元素无序，但是可以对元素进行快速的访问和删除。
    那么，它俩结合起来就兼具了哈希集合和链表的特性，既可以在 O(1) 时间内访问或删除其中的元素，又可以保持插入的时序
*/

class LFUCache {
    // key 到 val 的映射，我们后文称为 KV 表
    HashMap<Integer, Integer> keyToVal;

    // key 到 freq 的映射，我们后文称为 KF 表
    HashMap<Integer, Integer> keyToFreq;

    // freq 到 key 列表的映射，我们后文称为 FK 表
    HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;

    // 记录最小的频次
    int minFreq;

    // 记录 LFU 缓存的最大容量
    int cap;

    public LFUCache(int capacity) {
        keyToVal = new HashMap<>();
        keyToFreq = new HashMap<>();
        freqToKeys = new HashMap<>();
        this.cap = capacity;
        this.minFreq = 0;
    }

    public int get(int key) {
        if (!keyToVal.containsKey(key)) {
            return -1;
        }

        // 增加 key 对应的 freq
        increaseFreq(key);

        return keyToVal.get(key);
    }

    public void put(int key, int val) {
        if (this.cap <= 0) return;

        // 若 key 已存在，修改对应的 val 即可
        if (keyToVal.containsKey(key)) {
            keyToVal.put(key, val);

            // key 对应的 freq 加一
            increaseFreq(key);

            return;
        }

        // key 不存在，需要插入

        // 容量已满的话需要淘汰一个 freq 最小的 key
        if (this.cap <= keyToVal.size()) {
            removeMinFreqKey();
        }

        // 插入 KV 表
        keyToVal.put(key, val);

        // 插入 KF 表，对应的 freq 为 1
        keyToFreq.put(key, 1);

        // 初始化 FK 表
        freqToKeys.putIfAbsent(1, new LinkedHashSet<>());

        freqToKeys.get(1).add(key);

        // 插入新 key 后最小的 freq 肯定是 1
        this.minFreq = 1;
    }


    private void removeMinFreqKey()
    {
        // freq 最小的 key 列表
        LinkedHashSet<Integer> keyList = freqToKeys.get(this.minFreq);

        // 其中最先被插入的那个 key 就是该被淘汰的 key
        int deletedKey = keyList.iterator().next();

        // 更新 FK 表
        keyList.remove(deletedKey);
        if (keyList.isEmpty()) {
            freqToKeys.remove(this.minFreq);
            // 问：这里需要更新 minFreq 的值吗？
        }

        // 移除 KV 表
        keyToVal.remove(deletedKey);

        // 移除 KF 表
        keyToFreq.remove(deletedKey);
    }

    private void increaseFreq(int key) {
        int freq = keyToFreq.get(key);

        // 更新 KF 表
        keyToFreq.put(key, freq + 1);

        // 更新 FK 表
        // 将 key 从 freq 对应的列表中删除
        freqToKeys.get(freq).remove(key);
        // 如果 freq 对应的列表空了，移除这个 freq
        if (freqToKeys.get(freq).isEmpty()) {
             freqToKeys.remove(freq);
             // 如果这个 freq 恰好是 minFreq，更新 minFreq
             if (freq == this.minFreq) {
                 this.minFreq++;
             }
        }
        // 将 key 加入 freq + 1 对应的列表中
        freqToKeys.putIfAbsent(freq + 1, new LinkedHashSet<>());
        freqToKeys.get(freq + 1).add(key);
    }
}